/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:${USER}
 * Date:${YEAR}-${MONTH}-${DAY}
 * ${TIME}
 */
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
    public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


    public void reorderList(ListNode head) {
        ListNode slow=head,fast=head;
        ListNode cur=head;
        while(fast!=null||fast.next!=null){//找中间
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode prev=new ListNode(0);
         cur =slow.next;
         slow.next=null;
         while(cur!=null){//逆序中间点以后的链表（不包括中间点
             ListNode next=cur.next;
             cur.next=prev.next;
             prev.next=cur;
             cur=next;
         }

         ListNode ret1=head;
         ListNode ret2=prev.next;
         ListNode tmp=new ListNode(0);
         while(ret1!=null){//连接两段链表
             ListNode next=ret1.next;
             ret1.next=null;
             tmp.next=ret1;
             ret1=next;

             tmp=tmp.next;
             //连第二段
            if(ret2!=null){
                ListNode next1=ret2.next;
                ret2.next=null;
                tmp.next=ret2;
                ret2=next1;
                tmp=tmp.next;
            }
         }
    }

}